Search for: All records

Narrative planning is the process of generating sequences of actions that form coherent and goal-oriented narratives. Classical implementations of narrative planning rely on heuristic search techniques to offer structured story generation but face challenges with scalability due to large branching factors and deep search requirements. Large Language Models (LLMs), with their extensive training on diverse linguistic datasets, excel in understanding and generating coherent narratives. However, their planning ability lacks the precision and structure needed for effective narrative planning. This paper explores a hybrid approach that uses LLMs as heuristic guides within classical search frameworks for narrative planning. We compare various prompt designs to generate LLM heuristic predictions and evaluate their performance against h+, hmax, and relaxed plan heuristics. Additionally, we analyze the ability of relaxed plans to predict the next action correctly, comparing it to the LLMs’ ability to make the same prediction. Our findings indicate that LLMs rarely exceed the accuracy of classical planning heuristics. 

Traffic Stop is a virtual reality de-escalation training simulation for police officers that has an interactive story driven by artificial intelligence. This project was funded by the U.S. National Science Foundation and led by Prof. Stephen Ware of the Narrative Intelligence Lab at the University of Kentucky. 

Player goals in games are often framed in terms of achieving something in the game world, but this framing can fail to capture goals centered on the player’s own mental model, such as seeking the answers to questions about the game world. We use a least-commitment model of interactive narrative to characterize these knowledge goals and the problem of knowledge goal recognition. As a first attempt to solve the knowledge goal recognition problem, we adapt a classical goal recognition paradigm, but in our empirical evaluation the approach suffers from a high rate of incorrectly rejecting a synthetic player’s true goals; we discuss how handling of player goals could be made more robust in practice. 

Narrative planning generates a sequence of actions which must achieve the author's goal for the story and must be composed only of actions that make sense for the characters who take them. A causally necessary action is one that would make the plan impossible to execute if it were left out. We hypothesize that action sequences which are solutions to narrative planning problems are more likely to feature causally necessary actions than those which are not solutions. In this paper, we show that prioritizing sequences with more causally necessary actions can lead to solutions faster in ten benchmark story planning problems. 

We present an intelligent experience management architecture for a virtual reality police de-escalation training platform we are currently developing. Our aim is to direct the cast of non-player characters toward a scenario outcome appropriate to the player’s decisions, resulting in bad endings precisely when player’s mistakes enable them. We use a narrative planner to generate a story graph representing every possible narrative, and then we prune the graph to eliminate less believable non-player character actions. Unlike previous approaches based on story graph pruning, we implement an emotional planning model that lets us represent characters acting out of fear of bad outcomes as well as hope for good ones. We also incorporate experience management techniques for delaying commitment to hidden settings of the scenario and for capitalizing on player mistakes to demonstrate the negative consequences of not following best practices. 

Psychological research has demonstrated that as we experience a story several features affect the salience of its events in memory. These features correspond to who? where? when? how? and why? questions about those events. Computational models of salience have been used in interactive narratives to measure which events people most easily remember from the past and which they expect more readily from the future. We use three example domains to show that events in sequences that are solutions to narrative planning problems are generally more salient with each other, and events in non-solution sequences are less salient with each other. This means that measuring the salience of a sequence of actions during planning can serve as an efficient cost function to improve the speed, and perhaps also the quality, of a narrative planner. 

Narrative planners generate sequences of actions that represent story plots given a story domain model. This is a useful way to create branching stories for interactive narrative systems that maintain logical consistency across multiple storylines with different content. There is a need for story comparison techniques that can enable systems like experience managers and domain authoring tools to reason about similarities and differences between multiple stories or branches. We present an algorithm for summarizing narrative plans as numeric vectors based on a cognitive model of human story perception. The vectors encode important story information and can be compared using standard distance functions to quantify the overall semantic difference between two stories. We show that this distance metric is highly accurate based on human annotations of story similarity, and compare it to several alternative approaches. We also explore variations of our method in an attempt to broaden its applicability to other types of story systems. 

We present an intelligent experience management architecture for a virtual reality police de-escalation training platform we are currently developing. Our aim is to direct the cast of non-player characters toward a scenario outcome appropriate to the player’s decisions, resulting in bad endings precisely when player’s mistakes enable them. We use a narrative planner to generate a story graph representing every possible narrative, and then we prune the graph to eliminate less believable non-player character actions. Unlike previous approaches based on story graph pruning, we implement an emotional planning model that lets us represent characters acting out of fear of bad outcomes as well as hope for good ones. We also incorporate experience management techniques for delaying commitment to hidden settings of the scenario and for capitalizing on player mistakes to demonstrate the negative consequences of not following best practices. 

Intelligent interactive narrative systems coordinate a cast of non-player characters to make the overall story experience meaningful for the player. Narrative generation involves a tradeoff between plot-structure requirements and quality of character behavior, as well as computational efficiency. We study this tradeoff using the example of benchmark problems for narrative planning algorithms. A typical narrative planning problem calls for a sequence of actions that leads to an overall plot goal being met, while also requiring each action to respect constraints that create the appearance of character autonomy. We consider simplified solution definitions that enforce only plot requirements or only character requirements, and we measure how often each of these definitions leads to a solution that happens to meet both types of requirements—i.e., the density with which narrative plans occur among plot- or character-requirement-satisfying sequences. We then investigate whether solution densities can guide the selection of narrative planning algorithms. We compare the performance of two search strategies: one that satisfies plot requirements first and checks character requirements afterward, and one that continuously verifies character requirements. Our results show that comparing solution densities does not by itself predict which of these search strategies will be more efficient in terms of search nodes visited, suggesting that other important factors exist. We discuss what some of these factors could be. Our work opens further investigation into characterizing narrative planning algorithms and how they interact with specific domains. The results also highlight the diversity and difficulty of solving narrative planning problems. 

Sabre is a narrative planner—a centralized, omniscient decision maker that solves a multi-agent storytelling problem. The planner has an author goal it must achieve, but every action taken by an agent must make sense according to that agent’s individual intentions and limited, possibly wrong beliefs. This paper describes the implementation of Sabre, which supports a rich action syntax and imposes no arbitrary limit on the depth of theory of mind. We present a search procedure for generating plans that achieve the author goals while ensuring all agent actions are explained, and we report the system’s performance on several narrative planning benchmark problems.